import Data.Maybe
import Data.List

-- 1

type Country = String
type Countries = [Country]
type TravelTime = Integer
data Connection = Air Country Country TravelTime
                | Sea Country Country TravelTime
                | Rail Country Country TravelTime
                | Road Country Country TravelTime deriving (Eq,Ord,Show)
type Connections = [Connection]
data Itinerary = NoRoute | Route (Connections,TravelTime) deriving (Eq,Ord,Show)

-- DISCLAIMER
--
-- THIS SOLUTION IS EXTREMLY DIRTY AND EVEN INEFFICIENT
-- REFACTOR AND CLEAN UP!!!

neighbors :: Connections -> Country -> [(Country,TravelTime,Connection)]
neighbors conns c = mapMaybe neighbor conns
  where
    neighbor conn@(Air a b t)
      | a == c = Just (b,t,conn)
      | b == c = Just (a,t,conn)
      | otherwise = Nothing
    neighbor conn@(Sea a b t)
      | a == c = Just (b,t,conn)
      | b == c = Just (a,t,conn)
      | otherwise = Nothing
    neighbor conn@(Rail a b t)
      | a == c = Just (b,t,conn)
      | b == c = Just (a,t,conn)
      | otherwise = Nothing
    neighbor conn@(Road a b t)
      | a == c = Just (b,t,conn)
      | b == c = Just (a,t,conn)
      | otherwise = Nothing

groundNeighbors :: Connections -> Country -> [(Country,TravelTime,Connection)]
groundNeighbors conns c = mapMaybe neighbor conns
  where
    neighbor (Air a b t) = Nothing
    neighbor (Sea a b t) = Nothing
    neighbor conn@(Rail a b t)
      | a == c = Just (b,t,conn)
      | b == c = Just (a,t,conn)
      | otherwise = Nothing
    neighbor conn@(Road a b t)
      | a == c = Just (b,t,conn)
      | b == c = Just (a,t,conn)
      | otherwise = Nothing

yieldGroundReachable :: Connections -> Country -> Countries
yieldGroundReachable conns c = nub $ yieldGroundReachable' conns c []

yieldGroundReachable' :: Connections -> Country -> Countries -> Countries
yieldGroundReachable' conns c visited
  | elem c visited = []
  | otherwise = c : concat [yieldGroundReachable' conns n (c:visited) |
                            (n,_,_) <- groundNeighbors conns c]

yieldReachable :: Connections -> Country -> Countries
yieldReachable conns c = nub $ yieldReachable' conns c []

yieldReachable' :: Connections -> Country -> Countries -> Countries
yieldReachable' conns c visited
  | elem c visited = []
  | otherwise = c : concat [yieldReachable' conns n (c:visited) |
                            (n,_,_) <- neighbors conns c]

getAllCountries conns = nub $ concat $ map f conns
  where
    f (Air a b _) = [a,b]
    f (Sea a b _) = [a,b]
    f (Rail a b _) = [a,b]
    f (Road a b _) = [a,b]

yieldUnreachable :: Connections -> Country -> Countries
yieldUnreachable conns c = allCountries \\ reachableCountries
  where
    allCountries = getAllCountries conns

    reachableCountries = yieldReachable conns c


yieldRoutes :: Connections -> Country -> Countries -> (Connections,TravelTime) -> [(Connections,TravelTime)]
yieldRoutes conns c visited rt@(route,t)
  | elem c visited = []
  | otherwise = rt : concat [yieldRoutes conns n (c:visited) (route ++ [conn],t + t') |
                             (n,t',conn) <- neighbors conns c]

yieldCompleteTrips :: Connections -> Country -> [Itinerary]
yieldCompleteTrips conns c
  | null completeRoutes = [NoRoute]
  | otherwise = map (\rt -> Route rt) $ sort $ nub $ completeRoutes
  where
    numberOfCountries = length $ getAllCountries conns

    completeRoutes = filter (\(conns',_) -> (length conns') + 1 == numberOfCountries) $
                     yieldRoutes conns c [] ([],0)


isRoundTrip' :: Connections -> Country -> Countries -> Country -> Int -> [Bool]
isRoundTrip' conns c visited start completeLength
  | (length visited == completeLength) && start == c = [True]
  | elem c visited = [False]
  | otherwise = concat [isRoundTrip' conns n (c:visited) start completeLength |
                        (n,_,_) <- neighbors conns c]

isRoundTrip :: Connections -> Country -> Bool
isRoundTrip conns c = or $ isRoundTrip' conns c [] c numberOfCountries
  where
    numberOfCountries = length $ getAllCountries conns

-- 2

removeNthElem :: [a] -> Int -> [a]
removeNthElem xs i = ps ++ ts
  where
    ps = take (i - 1) xs
    ts = removeNthElem (drop i xs) i

sieveLuckyNumbers :: [Integer] -> Integer -> [Integer]
sieveLuckyNumbers ls n = n : sieveLuckyNumbers sieved n'
  where
    n' = head $ dropWhile (<= n) ls

    sieved = removeNthElem ls (fromInteger n')

luckyNumbers :: [Integer]
luckyNumbers = tail $ sieveLuckyNumbers [1,3..] 1

-- 3

isLuckyNumber :: Integer -> Bool
isLuckyNumber i = (head $ dropWhile (< i) luckyNumbers) == i

yieldLuckyNumbers :: Integer -> Integer -> [Integer]
yieldLuckyNumbers m n
  | m > n = []
  | otherwise =  takeWhile (<= n) $ dropWhile (< m) luckyNumbers

isTwinLuckyNumber :: Integer -> Bool
isTwinLuckyNumber n = isLuckyNumber n &&
                      (isLuckyNumber (n+2) || isLuckyNumber (n-2))

-- EOF --
